package hit.edu.zjc.Tool;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Set;

public class Algorithm
{
	public static void main(String[] args)
	{
		//1
		HashSet<Integer>set1=new HashSet<Integer>();
		set1.add(1);
		//2
		HashSet<Integer>set2=new HashSet<Integer>();
		set2.add(1);
		set2.add(2);
		//3
		HashSet<Integer>set3=new HashSet<Integer>();
		set3.add(1);
		set3.add(2);
		set3.add(3);
		//4
		HashSet<Integer>set4=new HashSet<Integer>();
		set4.add(1);
		set4.add(2);
		set4.add(3);
		set4.add(4);
		//5
		HashSet<Integer>set5=new HashSet<Integer>();
		set5.add(1);
		set5.add(2);
		set5.add(3);
		set5.add(4);
		set5.add(5);
		
		ArrayList<HashSet<Integer>>SetList=new ArrayList<HashSet<Integer>>();
		SetList.add(set1);
		SetList.add(set2);
		SetList.add(set3);
		SetList.add(set4);
		SetList.add(set5);
		
		System.out.println("before");
		for(int i=0;i<SetList.size();i++)
		{
			HashSet<Integer>set=SetList.get(i);
			System.out.println("第"+(i+1)+"个set的size："+set.size());
		}
		
		
		ArrayList<HashSet<Integer>>[] SetList_array=OptimizePartition(SetList,8);
		
		
		System.out.println("after");
		for(int i=0;i<SetList_array.length;i++)
		{
			ArrayList<HashSet<Integer>> SetList1=SetList_array[i];
			int sum=0;
			for(int k=0;k<SetList1.size();k++)
			{
				HashSet<Integer>set=SetList1.get(k);
				System.out.println("第"+(i+1)+"组：第"+(k+1)+"个set的size："+set.size());
				sum=sum+set.size();
			}
			System.out.println((i+1)+"th:"+sum);
			
		}
		
	}
	
	/*
	 * islow=true 降序排列
	 * islow=false 生序排列
	 * 
	 * */
	public static ArrayList<HashSet<Integer>> sortSetList(ArrayList<HashSet<Integer>> SetList,boolean islow)
	{
		Comparator<HashSet<Integer>> comparator=null;
		if(islow)
		{
			comparator=new Comparator<HashSet<Integer>>(){
				
				public int compare(HashSet<Integer> set1,HashSet<Integer> set2)
				{
					return set2.size()-set1.size();
				}
				
			};
		}
		else
		{
			comparator=new Comparator<HashSet<Integer>>(){
				
				public int compare(HashSet<Integer> set1,HashSet<Integer> set2)
				{
					return set1.size()-set2.size();
				}
				
			};
		}
		Collections.sort(SetList,comparator);
		return SetList;
			
	}
	
	/*
	 * 输入：一个集合，分组数量。
	 * 输出，k个组，每组的set的数量的和最接近平均值。
	 * 此问题是NP问题，用贪心法来做，不能保证找到的是最优的解。
	 * */
	public static ArrayList<HashSet<Integer>>[] OptimizePartition(ArrayList<HashSet<Integer>> SetList,int k)
	{
		//将SetList按set的size从大到小排列。
		SetList=sortSetList(SetList,true);
		
		int[] sum=new int[k];//存储每个组当前的和。
		for(int i=0;i<k;i++)
		{
			sum[i]=0;//初始化
		}
		
		ArrayList<HashSet<Integer>>[] SetList_array=(ArrayList<HashSet<Integer>>[])Array.newInstance(ArrayList.class,k);
		for(int i=0;i<k;i++)
		{
			SetList_array[i]=new ArrayList<HashSet<Integer>>();//初始化
		}
		
		//下面使用贪心法，进行分配。
		for(int i=0;i<SetList.size();i++)
		{
			HashSet<Integer>set=SetList.get(i);
			int min_index=Min(sum);
			SetList_array[min_index].add(set);
			sum[min_index]+=set.size();
		}
		
		return SetList_array;
	}
	
	/*
	 * 输入：整数数组
	 * 返回：最小的数的索引值
	 * */
	private static int Min(int[] array)
	{
		if(array.length==0)
			return -1;
		int min=array[0];
		int index=0;
		for(int i=1;i<array.length;i++)
		{
			if(array[i]<min)
			{
				min=array[i];
				index=i;
			}
		}
		return index;
		
	}

}
